//
// Description: 22. 括号生成
// Created by Loading on 2022/4/3.
//

#include <bits/stdc++.h>

using namespace std;

vector<string> generateParenthesis(int n) {
    vector<string> res;

    // 回溯，left为左括号数量，right为右括号数量
    function<void(int, int, string)> backtrack = [&](int left, int right, string s) {
        if (s.size() == 2 * n) {
            res.emplace_back(s);
        } else {
            if (left < n) {
                s += '(';
                backtrack(left + 1, right, s);
                s.pop_back();
            }
            if (right < left) {
                s += ')';
                backtrack(left, right + 1, s);
                s.pop_back();
            }
        }
    };

    string s;
    backtrack(0, 0, s);

    return res;
}

int main() {
    int n = 4;
    auto res = generateParenthesis(n);
    for (const auto &s : res) {
        cout << s << endl;
    }

    return 0;
}